package _01_排序;

import _01_排序.tools.Asserts;
import _01_排序.tools.Integers;

/*
    插入排序.时间复杂度仍然是O(n^2),稳定的排序

    ◼ 执行流程
    ① 在执行过程中，插入排序会将序列分为2部分
    ✓ 头部是已经排好序的，尾部是待排序的
    ② 从头开始扫描每一个元素
    ✓ 每当扫描到一个元素，就将它插入到头部合适的位置，使得头部数据依然保持有序
 */
public class InsertionSort04<E extends Comparable<E>> extends Sort<E>{
    /**
     * 默认第一个是有序的，从第二个开始
     * 使用二分搜索进行优化,渐少了比较次数
     */
    @Override
    protected void sort() {
        for(int begin = 1;begin<array.length;++begin){
            insert(begin,search(begin));
        }
    }

    /**
     * 找到index位置上的元素在有序数组中的待插入位置
     * 当前数组已经排好顺序的范围是[0,index)
     * @param index
     * @return
     */
    private int search(int index){
        int begin = 0;
        int end = index;
        while(begin<end){
            int mid = (begin+end) >> 1;
            if(cmp(array[index],array[mid])<0){
                end = mid;
            }else{ //包括了v >= array[mid]
                begin = mid + 1;
            }
        }
        return begin;
    }


    /**
     * 将数组元素进行插入，找到插入位置后，要先移动元素,在插入
     * @param source:源索引
     * @param dest:目标索引
     */
    private void insert(int source,int dest){
        E element = array[source]; //备份
        //移动元素
        for(int i=source;i>dest;--i){
            array[source] = array[source - 1];
        }
        //最终将待插入元素放入目标索引即可
        array[dest] = element;
    }


    private void sortSearch(E[] array){
        for(int begin=1;begin< array.length;++begin){
            ins(begin,sear(begin,array),array);
        }
    }

    private int sear(int index,E[] array){
        int begin = 0;
        int end = array.length;
        while(begin<end){
            int mid = (begin+end) >> 1;
            if(cmp(array[index],array[mid])<0){
                end = mid;
            }else{
                begin = mid+1;
            }
        }
        return begin;
    }

    private void ins(int source,int dest,E[] array){
        E element = array[source];
        for(int i=source;i>dest;i--){
            array[source] = array[source-1];
        }
        array[dest] = element;
    }



    /*
        插入排序,无忧化版
     */
    /*@Override
    protected void sort() {
        for(int begin = 1;begin<array.length;++begin){
            //找一个变量替代当前索引，防止这一轮比较完以后，下一个索引丢失
            int cur = begin;
            E element = array[cur]; //记录当前比较元素
            while (cur > 0 && cmp(element,array[cur-1])<0){
                //减少交换次数,将大的元素往后挪动
                array[cur] = array[cur-1];
                //要不断的往前进行比较，直到找到合适的位置
                cur--;
            }
            //最后将备份元素放到合适位置
            array[cur] = element;
        }
    }*/

    public static void main(String[] args) {
        Integer[] array = Integers.random(50,100,500);
        new InsertionSort04<Integer>().sortSearch(array);
        Asserts.test(Integers.isAscOrder(array));
    }
}
